1154G - Minimum Possible LCM - CodeForces Solution

#include "bits/stdc++.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int long long
#define pb push_back
#define fi first
#define se second
#define el '\n'
#define ss ' '
#define ll long long
#define vii vector<pair<int,int>>
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define rall(a) a.rbegin(),a.rend()
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define popcount(x) __builtin_popcount(x)
#define zedanPasha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define clr(x,y) memset(x,y,sizeof(x))

template<typename T=int>
istream& operator >>(istream& in,vector<T>& a)
{
    for(T&i:a) cin>>i;
    return in;
}
template<typename T=int>
ostream& operator <<(ostream& out,vector<T>& a)
{
    for(T&i:a) cout<<i<<ss;
    return out;
}
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

int dx[] = {0, 0, -1, 1};//right,left,up,down
int dy[] = {1, -1, 0, 0};

bool valid(int r, int c, int R, int C)
{
    if (r < 0 || r >= R || c < 0 || c >= C)
        return false;
    return true;
}

ll fp(ll a, ll b)
{
    ll ans=1;
    while (b)
    {
        if(b&1)
            ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
int n;
vi a;
int const N = 1e7 + 5;
int mp[N];

int f,s;
void sieve()
{
    ll mn = LLONG_MAX;
    for(int i=1 ; i<=N ; i++)
    {
        ll sm1=0,sm2=0;
        for(int j=i ; j<N ; j+=i)
        {
            if(mp[j])
            {
                int cnt = mp[j];
                if(!sm1)
                {
                    sm1 = j;
                    if(cnt-1)
                    {
                        sm2 = j;
                        break;
                    }
                }
                else
                {
                    sm2 = j;
                    break;
                }
            }
        }
        ll cur = (sm1*sm2)/i;
        if(sm1 && sm2 && mn>cur)
        {
            f = sm1,s = sm2;
            mn = cur;
        }
    }
}
void doWork()
{
    cin>>n;
    a.resize(n);
    for(int i=0 ; i<n ; i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    sieve();
    vll ans;
    for(int i=0 ; i<n ; i++)
    {
        if(a[i]==f)
        {
            ans.pb(i+1);
            f=-1;
        }
        else if(a[i]==s)
        {
            ans.pb(i+1);
            s=-1;
        }
        if(sz(ans)==2)
            break;
    }
    sort(all(ans));
    cout<<ans;
}

signed main()
{
    zedanPasha
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    //cin >> t;
    while (t--)
        doWork();
    return 0;
}